import bisect
from typing import *
from math import inf


class SegmentTree:

    def __init__(self, ceil: int = None, nums: List[int] = None) -> None:
        self.nums = nums
        self.n = ceil if ceil is not None else len(nums)
        self.ands = [0] * (self.n << 2)
        if nums is not None:
            self.build(0, self.n - 1, 1)

    def build(self, s: int, e: int, node: int):
        if s == e:
            self.ands[node] = self.nums[s]
            return
        m = s + ((e - s) >> 1)
        self.build(s, m, node << 1)
        self.build(m + 1, e, node << 1 | 1)
        self.ands[node] = self.ands[node << 1] & self.ands[node << 1 | 1]

    def query_and(self, L: int, R: int) -> int:
        return self.__query_and(0, self.n - 1, 1, L, R)

    def __query_and(self, s: int, e: int, node: int, L: int, R: int):
        if L <= s and e <= R:
            return self.ands[node]
        # self.__pushdown(s, e, node)
        m = ((e - s) >> 1) + s
        ans = -1
        if L <= m:  # 左边有任务
            ans &= self.__query_and(s, m, node << 1, L, R)
        if m < R:  # 右边有任务
            ans &= self.__query_and(m + 1, e, node << 1 | 1, L, R)
        return ans


class SegmentTreeMN:

    def __init__(self, ceil: int = None, nums: List[int] = None) -> None:
        self.nums = nums
        self.n = ceil if ceil is not None else len(nums)
        self.mns = [inf] * (self.n << 2)
        if nums is not None:
            self.build(0, self.n - 1, 1)

    def build(self, s: int, e: int, node: int):
        if s == e:
            self.mns[node] = self.nums[s]
            return
        m = s + ((e - s) >> 1)
        self.build(s, m, node << 1)
        self.build(m + 1, e, node << 1 | 1)
        self.mns[node] = min(self.mns[node << 1], self.mns[node << 1 | 1])

    def query_mn(self, L: int, R: int) -> int:
        return self.__query_mn(0, self.n - 1, 1, L, R)

    def __query_mn(self, s: int, e: int, node: int, L: int, R: int):
        # print(s, e, L, R)
        if L <= s and e <= R:
            return self.mns[node]
        m = ((e - s) >> 1) + s
        ans = inf
        if L <= m:  # 左边有任务
            ans = min(ans, self.__query_mn(s, m, node << 1, L, R))
        if m < R:  # 右边有任务
            ans = min(ans, self.__query_mn(m + 1, e, node << 1 | 1, L, R))
        return ans


class Solution:
    def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
        n, m = len(nums), len(andValues)
        f = [1000000] * n
        a = -1
        for i, num in enumerate(nums):
            a &= num
            if a == andValues[0]:
                f[i] = nums[i]
        st = SegmentTree(nums=nums)
        for i in range(1, m):
            c = [1000000] * n
            mnst = SegmentTreeMN(nums=f)
            for j in range(i, n):
                l = bisect.bisect_left(
                    range(j + 1), andValues[i], key=lambda a: st.query_and(a, j)
                )
                r = (
                    bisect.bisect_right(
                        range(j + 1), andValues[i], key=lambda a: st.query_and(a, j)
                    )
                    - 1
                )
                if r >= l:
                    mn = 1000000 if l == 0 and r == 0 else mnst.query_mn(l - 1, r - 1)
                    c[j] = min(mn + nums[j], c[j])  # nums[j]

            f = c
        return f[-1] if f[-1] < 1000000 else -1


s = Solution()
print(s.minimumValueSum([1, 2, 5, 6], [1, 0]))
print(s.minimumValueSum([4, 8, 9], [0]))
print(s.minimumValueSum([2, 10, 2], [2, 2]))
print(s.minimumValueSum([1, 1, 1], [1, 1]))
print(s.minimumValueSum(nums=[1, 4, 3, 3, 2], andValues=[0, 3, 3, 2]))
print(s.minimumValueSum(nums=[2, 3, 5, 7, 7, 7, 5], andValues=[0, 7, 5]))
